1. Field
Example embodiments of the present invention relate to a computer readable storage medium having a data operation program for data having a list structure recorded thereon, and a data processing apparatus; and more specifically to a computer readable storage medium having a data processing program for executing data search, addition and delete processing for a sorted linked list, and a data processing apparatus.
2. Description of the Background Art
Conventionally, there is a data structure referred to as a “skip list”, which is devised as a substitute for a so-called balanced tree (for example, “UNIX MAGAZINE”, January 1999, pp. 68-80, published by Kabushiki Kaisha ASCII; herein after, referred to as “Non-patent document 11”). As compared to a balanced tree, a skip list is advantageous in being a simpler data structure and in being mountable more easily. FIG. 54 shows an exemplary data structure of such a skip list. As shown in FIG. 54, a skip list is a linked list having a plurality of pointers. In other words, a skip list has layers of lists. The lowest layer is a usual sorted linked list. The upper layers act like an “express train” owing to the plurality of pointers. The number of pointers included in each element is determined using a predetermined value of probability p (0≦p≦1) and random numbers when each element is assigned (added). In the skip list, the i'th pointer from the bottom of each element represents the next element having i or a larger number of pointers. In addition, as shown in FIG. 54, the skip list has special elements, which are a “header” representing the first element of the skip list and a “NIL” representing the final element of the skip list.
In the skip list, in order to search for a target element, scanning is performed from the first element of the skip list until the final element among the elements of a value which is equal to, of a smaller than, the target element. FIG. 55 shows a search path for searching for a “19” element as a search target. In FIG. 55, a search is started from the highest layer of the “header”. When the value of the search target (“19”) is larger than the value of the element indicated by the pointer (“6”), the pointers of the same height are searched for sequentially. When the search in this layer reaches “NIL”, the search is transferred to the next lower layer, and the pointes in this layer are searched for sequentially (searched for as “6”→“25”). When the value of the search target is smaller than, or equal to, the value of the element indicated by the pointer, the search is not transferred to the next element and transferred to the next lower layer, and the pointers in this layer are searched for sequentially (the search is not transferred to the element of “25” but is transferred to the next lower layer of the element of “16”). Such a search is continued, and when the search reaches the lowest layer, the element immediately to the right thereof is the desired element. If the value of this element matches the value of the search target, the search is successful; where as if the values do not match each other, the search fails. In this manner, unlike a sequential search from the first element, the skip list allows the intermediate elements to be skipped. The average calculation amount required for the search by the skip list is O (log n), which is the same as that required by the balanced tree.
However, the above-described skip list disclosed in Non-patent document 1 has the following problems First, the specifications of the skip list do not allow an access to a position specified by the number of elements from the beginning, for example, an access to “the n'th data from the beginning” (herein after, such an access will be referred to as an “index access”). Namely, in the skip list, each element has its own data and information regarding “to which element each element is linked (pointer)”, but does not have information regarding “at which position each element is positioned from the beginning”. Therefore, the structure of the skip list does not allow the index access.
The number of pointers included in each element is determined using random numbers as described above, and the order in the skip list depends on the performance of the random numbers. Theoretically, the order in the skip list is O (log n), which is the same as that in the balanced tree, but when the random numbers become unbalanced, the order may be deteriorated. There may be a case where the order is always worst.
When only the elements having a large number of pointers are deleted, or when only the elements having a small number of pointers are deleted, the above-described performance of O (log n) cannot be provided. For example, referring to FIG. 54, when only the low elements (elements having a small number of pointers) are deleted, the number of elements which can be skipped is decreased. As a result, the performance of O (logon cannot be provided. When only the high elements (elements having a large number of pointers) in FIG. 54 are deleted, there is no significant difference from a simple linked list.